/**
 * @param {number} n
 * @return {number}
 */
// 动态规划
var numSquares = function (n) {
  const squares = []
  let i = 1;
  while (i * i <= n) {
    squares.push(i * i)
    i++
  }
  // 初始化表示没有解的情况
  const dp = new Array(n + 1).fill(n + 1)
  dp[0] = 0 // 0由0个完全平方数组成
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < squares.length; j++) {
      if (i - squares[j] >= 0 && dp[i - squares[j]] !== n + 1) {
        dp[i] = Math.min(dp[i], dp[i - squares[j]] + 1)
      }
    }
  }
  if (dp[n] === n + 1) return -1
  return dp[n]
};
// 广度优先算法（又是最短最少这种描述）
var numSquares = (n) => {
  const squares = []
  let i = 1;
  while (i * i <= n) {
    squares.push(i * i)
    i++
  }
  const queue = []
  const visited = new Array(n + 1).fill(false)
  queue.push(n)
  visited[n] = true
  let ans = 1
  while(queue.length > 0) {
    let l = queue.length
    for(let i = 0; i < l; i++) {
      let temp = queue.shift()
      for(let j = 0; j < squares.length; j++) {
        if(temp > squares[j] && !visited[temp - squares[j]]) {
          queue.push(temp - squares[j])
          visited[temp - squares[j]] = true
        }
        if(temp - squares[j] == 0) return ans
        if(temp - squares[j] < 0) break
      }
    }
    // 广度优先遍历遍历完一层深度+1
    ans++
  }
  return ans
}